package com.huawei.M01.iterator.A27;

import java.util.*;
import java.util.stream.Collectors;

/**
 * 最长字符串链
 *
 * @author 111
 */
public class StrChar {
    public int longestStrChain(String[] words) {
        Map<String, Integer> cache = new HashMap<>(words.length);
        Arrays.sort(words, Comparator.comparingInt(String::length));

        int res = 0;
        for (String word : words) {
            // 拆分word，找到最大长度
            // 最大长度为当前word的前一个的长度 + 1；
            int length = 1;
            for (int i = 0; i < word.length(); i++) {
                String str = word.substring(0, i) + word.substring(i + 1);
                if (cache.containsKey(str)) {
                    length= Math.max(length, cache.get(str) + 1);
                }

            }
            cache.put(word, length);
            res = Math.max(res, cache.get(word));
        }
        return res;
    }

    public static void main(String[] args) {
        System.out.println(new StrChar().longestStrChain(new String[]{"a","b","ba","bca","bda","bdca"}));
    }
}
